19. 删除链表的倒数第 N 个结点
19. 删除链表的倒数第 N 个结点
分析
这个题一看就得用递归，用递归的方式从后往前开始计数，找到倒数第 N+1 个节点，进行删除，同时因为链表头节点可能被删除，因此得用虚拟头节点法。大概就是这样的思路。
有没有更高级的办法呢？有！双指针法，这个是真的很难想到。没想到这里也能用到双指针法，
双指针法的思路很简单，首先把一个指针 fast 从头往后移动 n，头节点的位置为 1 的话，这个 fast 所在的位置就是 n,反过来倒着计数，假设 fast 指针的位置为 1 的话，反过来数，头节点就是 n，虚拟头节点 slow 就是 n+1,然后我们同步移动 slow 和 fast 这两个指针，那么当 fast 指向链表的最后一个元素的时候，slow 指向的就是倒数第 n+1 个节点，也就是待删除节点的前一个结点。
双指针法的精髓，就是先把快指针移动 n，然后再同时移动快指针和慢指针，知道快指针移动到链表的最后一个元素。非常巧妙
解题
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyNode = new ListNode(-1,head);
removeNode(dummyNode,n);
return dummyNode.next;
}
// 递归主要用来计数
public int removeNode(ListNode head,int n) {
if(head.next==null){
return 1;
}else{
int reverseIndex = removeNode(head.next,n)+1;
if(reverseIndex==(n+1)){
head.next = head.next.next;
}
return reverseIndex;
}
}
双指针法的实践，确实很简单，很高级
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode();
dummyHead.next = head;
ListNode fastNode = dummyHead;
// nowIndex 的定义是fast当前所在位置，位置的从1开始定义
int nowIndex = 0;
// 先移动快指针
while (nowIndex < n && fastNode != null) {
fastNode = fastNode.next;
nowIndex++;
}
// 退出循环的时候，nowIndex比n小，说明没到n，fastNode 就为null了，也就是说链表没那么长
if (nowIndex < n){
// 没有那么长
return head;
}
// 指向要删除节点的前一个节点
ListNode slowPreNode = dummyHead;
while(fastNode != null && fastNode.next != null){
// 同时移动
fastNode = fastNode.next;
slowPreNode = slowPreNode.next;
}
//删除
slowPreNode.next=slowPreNode.next.next;
return dummyHead.next;
}